package com.yang.Offer;

public class Offer19 {
    public static void main(String[] args) {
        String s = "aa";
        String p = "a*";
        Offer19Solution offer19Solution = new Offer19Solution();
        boolean match = offer19Solution.isMatch(s, p);
        System.out.println(match);

    }
}
class Offer19Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        // 如果不改变boolean数组 默认是false
        boolean[][] dp = new boolean[n + 1][m + 1];
        //dp[i][j]为考虑s[0,i-1],p[0,j-1]时,是否能匹配上,匹配上就为true
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++){
                if(j == 0){
                    // 对应为两字符串都为空串的时候肯定相等
                    dp[i][j] = i == 0;
                }else{
                    if(p.charAt(j - 1) != '*'){
                        // i 要>0 否则 i = 0也会跳进判断这样 会报错
                        if( i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                    else{
                        // 直接把C*当作0个C  就是跳过
                        if(j >= 2){
                            dp[i][j] = dp[i][j - 2];
                        }
                        // 计算比较 看的情况
                        if(i > 1 && j>=2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')){
                            // 因为对于 S对于P来说 在这样的情况下 s的字符串如果存在有一连串相等的情况,那么p需要保持原位把这些字符串全盘接受
                            dp[i][j] = dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }
}
//https://www.bilibili.com/video/BV1Br4y1v7SA?spm_id_from=333.337.search-card.all.click
// 主串为A, 匹配串为B
// 1. B分空串和 非空串两种情况  空串 则看A A若也为空串则true
// 2. 非空串往下走，是 * 与不是 *两种情况
// 2.1 若不是*  则是普通字符 或者 .  如果是普通字符则看 A(i-1)==?B(j-1) 如果是. 则直接看A(i-1)==?B(j-1)
// 2.2 如果是 * 则分 看和不看两种情况
//  看： 就是 如果B[j-1] == *
//  那么就在  A[i-1] == B[j-2] 或者B[j]==.的时候 看f[i-2][j] 因为对于j来说，在前面条件成立的情况下,一直到j都是成立的
// 所以只需要看 .* 前面的字符串是否匹配了
//  如果是不看,那么就是认为 B[j-2]与* 这两个字符是 0*C 就是说当作作废  直接看这两个字符之前的字符是否匹配
//
//
//

